题目分析

这是第217场周赛的第三题，这个题目难度较大，思路也非常奇特，小伙伴们之前应该都没有遇到过类似的题目，拿出来给小伙伴们看一看。

数学

这个题目我没有求解出来，参考了北大吴自华大佬的题解。

我们最终要让nums[i]+nums[n - 1 - i]等于同一个数target，那么不妨设
$$ nums[i] = a, nums[n - 1 - i] = b，a \le b$$
如果 a > b则可以交换a和b，不会影响结果。如[1, 2, 3, 4]和[4, 2, 3, 1]的结果是相同的。

我们让target从2开始移动，因为nums[i]都大于等于1。因此操作次数是2n。即target < 2的时候，在移动之前每一个操作数都需要改变。

发现如果$target = 1 + nums[k]$的时候，操作次数就会减少一次，只需要将nums[n - 1 - k]改成1即可，nums[k]不用变化。

发现如果$target = nums[k] + nums[n - 1 - k]$的时候，操作次数又会减少一次，因为两个都不需要变化。

发现如果$target = nums[k] + nums[n - 1 - k] + 1$的时候，操作次数会增加一次，因为需要将a改为a + 1。

发现如果$target = nums[n - 1 - k] + limit + 1$的时候，操作次数又会增加一次，因为需要将a变为limit，b变为b + 1。

只要从2到2*limit遍历target，求出最小的操作次数即可。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

#include<iostream>
#include<vector>
#include<algorithm>

class Solution {
public:
    int minMoves(vector<int>& nums, int limit) {
        vector<int> delta(limit * 2 + 2);
        int length = nums.size();
        for (int i = 0; i < length / 2; i++) {
            int low = 1 + min(nums[i], nums[length - i - 1]);
            int high = limit + max(nums[i], nums[length - i - 1]);
            int sum = nums[i] + nums[length - i - 1];
            delta[low]--;
            delta[sum]--;
            delta[sum + 1]++;
            delta[high + 1]++;
        }
        int res = length, cur = length;
        for (int i = 2; i <= limit * 2; i++) {
            cur += delta[i];
            res = min(res, cur);
        }
        return res;
    }
};

刷题总结

这个题目太奇妙了，如果遇到了这个题目，我相信小伙伴们也是非常困扰的，因此刷题的目的除了熟练代码，练习算法以外还能够拓展思维，开阔视野，非常nice。